/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/median
   @Language: C++
   @Datetime: 16-02-09 04:51
   */

// Method 1, Quick search, Time 30ms
class Solution {
	int quicksearch(vector<int> &A,int begin,int end,int mid){
		int low=begin, high=end-1, key;
		for(key=A[low]; low<high;){
			for(;low<high && A[high]>=key; --high);
			A[low] = A[high];
			for(;low<high && A[low]<=key; ++low);
			A[high] = A[low];
		}
		A[low] = key;
		if (low==mid) return key;
		if (low<mid) return quicksearch(A,low+1,end,mid);
		return quicksearch(A,begin,low,mid);
	}

public:
	/**
	 * @param nums: A list of integers.
	 * @return: An integer denotes the middle number of the array.
	 */
	int median(vector<int> &A) {
		// write your code here
		return quicksearch(A,0,A.size(),(A.size()-1)/2);
	}
};
